package yaoyuan.algorithm.tests;

public class FindMaxSubtraction {

	/**
	 * @param args
	 * @throws Exception 
	 */
	public static void main(String[] args) throws Exception {
		System.out.println(findMaxSubtraction(new int[]{100,13,99,2,7,3,101,16,8,4,20}));
	}

	public static int findMaxSubtraction(int[] inputs) throws Exception {
		if (inputs.length<=2)
			throw new Exception();
		
		int left = inputs[0];
		int right = inputs[1];
		int result = left - right;
		
		
		for (int i=2; i<inputs.length; i++){
			if (inputs[i]<=right){
				right = inputs[i];
				result = left - right;
			}else{
				if (inputs[i]>=result && inputs[i]>=left){
					left = inputs[i];
					if (i+1<inputs.length){
						
						if (left - inputs[i+1]>=result){
							result = left - inputs[i+1];
						}
						right = inputs[i+1];
						i++;
					}
				}
			}
		}
		
		return result;
	}
}
